/**
 * Created whit IntelliJ IDEA.
 * Description：
 * User：ZHONGCHEN
 * Date:2022-05-13
 * Time:21:33
 */

import com.sun.org.apache.regexp.internal.RE;
import com.sun.org.apache.xpath.internal.operations.Mod;
import org.omg.PortableServer.POA;

import java.text.SimpleDateFormat;
import java.util.*;
import java.util.function.Consumer;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;

/**
 * 题目:一次编辑
 * 字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。
 * 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。
 */
class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

public class TestDemo {
    public static void main1(String[] args) {
        String s1 = "intention";
        String s2 = "execution";
        System.out.println(oneEditAway(s1, s2));
    }

    public static boolean oneEditAway(String first, String second) {
        String s1 = first.length() > second.length() ? first : second;
        String s2 = first.length() > second.length() ? second : first;

        //如果两个字符串长度相差大于1;则返回false
        if (s1.length() - s2.length() > 1) {
            return false;
        }

        int i = 0;
        int j = 0;
        int cnt = 1;
        boolean ans = true;
        while (i < s1.length() && j < s2.length() && cnt >= 0) {
            //相同字符
            if (s1.charAt(i) == s2.charAt(j)) {
                i++;
                j++;
            } else {
                //字符长度相同;通过修改字符来达到相同
                if (s1.length() == s2.length()) {
                    i++;
                    j++;
                    cnt--;
                } else {
                    //字符串长度不同;通过插入或删除来修改字符
                    i++;
                    cnt--;
                }
            }
        }
        if (cnt < 0) {
            ans = false;
        }
        return ans;
    }

    public static void main3(String[] args) {
        letterCasePermutation("a1b2");
    }

    //784. 字母大小写全排列--回溯算法
//    输入：s = "a1b2"
//    输出：["a1b2", "a1B2", "A1b2", "A1B2"]
    public static List<String> letterCasePermutation(String s) {
        return buildStr(0, new ArrayList<String>(), s.toCharArray());
    }

    private static List<String> buildStr(int start, List<String> ans, char[] sc) {
        ans.add(new String(sc));
        for (int i = start; i < sc.length; i++) {
            if (sc[i] < 'A') {// sc[i]是数字，则不需要变化
                continue;
            }
            if (sc[i] >= 'a') {
                sc[i] = (char) (sc[i] - 32);//小写转大写
                buildStr(i + 1, ans, sc);
                sc[i] = (char) (sc[i] + 32);//回溯
            } else {
                sc[i] = (char) (sc[i] + 32);//大写转小写
                buildStr(i + 1, ans, sc);
                sc[i] = (char) (sc[i] - 32);//回溯
            }

        }
        return ans;
    }

    /**
     * 1662. 检查两个字符串数组是否相等--双指针
     * 输入：word1 = ["ab", "c"], word2 = ["a", "bc"]
     * 输出：true
     * 解释：
     * word1 表示的字符串为 "ab" + "c" -> "abc"
     * word2 表示的字符串为 "a" + "bc" -> "abc"
     * 两个字符串相同，返回 true
     *
     * @param word1
     * @param word2
     * @return
     */
    public boolean arrayStringsAreEqual(String[] word1, String[] word2) {
        int w1Length = word1.length, w2Length = word2.length;
        int left = 0, right = 0, w1 = 0, w2 = 0;
        while (w1 < w1Length && w2 < w2Length) {
            if (word1[w1].charAt(left++) != word2[w2].charAt(right++)) {
                return false;
            }
            if (left == word1[w1].length()) {
                left = 0;
                w1++;
            }
            if (right == word2[w2].length()) {
                right = 0;
                w2++;
            }
        }
        return w1 == w1Length && w2 == w2Length;
    }

    /**
     * 481. 神奇字符串
     * 可以把 sss 看成是由「111 组」和「222 组」交替组成的，
     * 重点在于每组内的数字是一个还是两个，这可以从 sss 自身上知道。
     * 注意最后一次构造可能会填入两个数，导致 sss 的长度为 n+1n+1n+1，
     * 因此最后统计 111 的个数时，应统计 sss 的前 nnn 个数，而不是整个 sss
     */
    public int magicalString(int n) {
        char[] s = new char[n + 2];
        s[0] = 1;
        s[1] = s[2] = 2;
        char c = 2;
        for (int i = 2, j = 3; j < n; ++i) {
            c ^= 3; // 1^3=2, 2^3=1，这样就能在 1 和 2 之间转换
            s[j++] = c;
            if (s[i] == 2) {
                s[j++] = c;
            }
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += 2 - s[i]; // 2-1=1，2-2=0，这样就只统计了 1
        }
        return ans;
    }

    public static void main4(String[] args) {
//        IntStream ints = new Random().ints(10);
//        System.out.println(ints);
//        IntStream intStream = ints.map(i -> Math.abs(i));
//        intStream.forEach(i->System.out.println(i));
//        IntStream intss = new Random().ints(10);
//        intss.map(Math::abs).forEach(System.out::println);
//        ints.close();

        List<UserInfo> userInfos = new ArrayList<>();
        userInfos.add(new UserInfo(1L, "11", 1));
        userInfos.add(new UserInfo(2L, "22", 2));
        userInfos.add(new UserInfo(2L, "33", 3));

        Set<UserInfo> collect = userInfos.stream().collect(Collectors.toSet());
        collect.forEach(a -> System.out.println(a.getAge() + " " + a.getName()));
        Map<Long, UserInfo> map = userInfos.stream().collect(Collectors.toMap(UserInfo::getId, userInfo -> userInfo, (k1, k2) -> k1));
        map.values().forEach(a -> System.out.println(a.getName()));
        map.keySet().forEach(a -> System.out.println(a));
        Function<UserInfo, String> getName = UserInfo::getName;
        System.out.println(getName);
        UserInfo userInfo = new UserInfo(2L, "33", 4);
    }

    /**
     * 1668. 最大重复子字符串
     *
     * @param sequence
     * @param word
     * @return
     */
    public static int maxRepeating(String sequence, String word) {
        int lengthS = sequence.length(), lengthW = word.length();
        if (!sequence.contains(word)) {
            return 0;
        }
        int ans = 0;
        int[] f = new int[lengthS + 10];
        for (int i = 1; i <= lengthS; i++) {
            if (i - lengthW < 0) {
                continue;
            }
            if (sequence.substring(i - lengthW, i).equals(word)) {
                f[i] = f[i - lengthW] + 1;
                ans = Math.max(ans, f[i]);
            }
        }
        return ans;
    }

    public static void main6(String[] args) {
        System.out.println(maxRepeating("aaaba aaab aaaba aaaba aaaba aaaba aaaba", "aaaba"));
    }

    /**
     * 1620. 网络信号最好的坐标
     * 建立一个大小为 110×110110 \times 110110×110 的棋盘 g，用于记录每个坐标点的信号值，
     * 即 g[i][j]=xg[i][j] = xg[i][j]=x 代表坐标 (i,j)(i, j)(i,j) 的信号值为 xxx
     * 其中 110110110 的大小是利用了「任意坐标 (x,y)(x, y)(x,y) 的取值范围不超过 505050」，
     * 同时「最远距离 kkk 不超过 505050」并且「最终答案为非负坐标」而定。
     * 枚举所有 towers[i]=(a,b,q)towers[i] = (a, b, q)towers[i]=(a,b,q)，并检查以该塔为中心点，
     * 大小为 ((k + k)^2的矩阵中的所有点（该塔所能贡献信号的所有坐标均落在矩阵中），枚举过程中使用变量
     * val 记录最大信号值，使用 x 和 y 记录答案坐标
     *
     * @param towers
     * @param radius
     * @return
     */
    public int[] bestCoordinate(int[][] towers, int radius) {
        int[][] g = new int[110][110];
        int x = 0, y = 0, val = 0;
        for (int[] t : towers) {
            int a = t[0], b = t[1], q = t[2];
            for (int i = Math.max(0, a - radius); i <= a + radius; i++) {
                for (int j = Math.max(0, b - radius); j <= b + radius; j++) {
                    double d = Math.sqrt((a - i) * (a - i) + (b - j) * (b - j));
                    if (d > radius) {
                        continue;
                    }
                    g[i][j] += Math.floor(q / (1 + d));
                    if (g[i][j] > val) {
                        x = i;
                        y = j;
                        val = g[i][j];
                    } else if (g[i][j] == val && (i < x || (i == x && j < y))) {
                        x = i;
                        y = j;
                    }
                }
            }
        }
        return new int[]{x, y};
    }

    /**
     * 1773. 统计匹配检索规则的物品数量--简单模拟
     *
     * @param items
     * @param ruleKey
     * @param ruleValue
     * @return
     */
    public static int countMatches2(List<List<String>> items, String ruleKey, String ruleValue) {
        int index = 0;
        int ans = 0;
        if ("type".equals(ruleKey)) {
            index = 0;
        } else if ("color".equals(ruleKey)) {
            index = 1;
        } else {
            index = 2;
        }
        for (List<String> i : items) {
            if (ruleValue.equals(i.get(index))) {
                ans++;
            }
        }
        return ans;
    }

    public static int countMatches1(List<List<String>> items, String ruleKey, String ruleValue) {
        final int[] ans = {0};
        int index = 0;
        if ("type".equals(ruleKey)) {
            index = 0;
        } else if ("color".equals(ruleKey)) {
            index = 1;
        } else {
            index = 2;
        }
        int finalIndex = index;
        items.forEach(list -> {
            if (list.get(finalIndex) == ruleValue) {
                ans[0]++;
            }
        });
        return ans[0];
    }

    public static int countMatches(List<List<String>> items, String ruleKey, String ruleValue) {
        int ans = 0, index = 0;
        if ("type".equals(ruleKey)) {
            index = 0;
        } else if ("color".equals(ruleKey)) {
            index = 1;
        } else {
            index = 2;
        }
        int finalIndex = index;
        List<List<String>> collect = items.stream()
                .filter((list) -> list.get(finalIndex).equals(ruleValue))
                .collect(Collectors.toList());
        return collect.size();
    }

    public static void main7(String[] args) {
        List<String> list = Arrays.asList(new String[]{"phone", "blue", "pixel"});
        List<String> list1 = Arrays.asList(new String[]{"computer", "silver", "lenovo"});
        List<String> list2 = Arrays.asList(new String[]{"phone", "gold", "iphone"});
        List<List<String>> list3 = Arrays.asList(list, list1, list2);
        System.out.println(countMatches1(list3, "color", "silver"));
    }

    /**
     * 754. 到达终点数字--【爪哇缪斯】图解LeetCode
     *
     * @param target
     * @return
     */
    public static int reachNumber(int target) {
        int ans = 0, num = 0;
        int t = Math.abs(target); // 由于target有负数情况，为了统一计算逻辑，所以取绝对值
        // 直到num值大于等于t，并且num减t是偶数，才结束while循环
        while (num < t || (num - t) % 2 != 0) {
            ans++;
            num += ans;
        }
        return ans;
    }

    public static void main8(String[] args) {
        System.out.println(reachNumber(2));
    }

    /***
     * 1106. 解析布尔表达式--单调栈
     * @param expression
     * @return
     */
    public static boolean parseBoolExpr(String expression) {
        Stack<Character> stack = new Stack<>();
        for (char c : expression.toCharArray()) {
            if (c != ')') {
                stack.push(c);
            } else {
                StringBuilder builder = new StringBuilder();
                while (stack.peek() != '(') {
                    builder.append(stack.pop());
                }
                stack.pop();
                char flag = stack.pop();
                if (flag == '|') {
                    if (builder.toString().contains("t")) {
                        stack.push('t');
                    } else {
                        stack.push('f');
                    }
                } else if (flag == '&') {
                    if (builder.toString().contains("f")) {
                        stack.push('f');
                    } else {
                        stack.push('t');
                    }
                } else {
                    if (builder.toString().contains("t")) {
                        stack.push('f');
                    } else {
                        stack.push('t');
                    }
                }
            }
        }
        if (stack.peek().equals('t')) {
            return true;
        }
        return false;
    }

    public static void main9(String[] args) {
        System.out.println(parseBoolExpr("|(&(t,f,t),!(t))"));
    }

    public static void main10(String[] args) {
        UserInfo userInfo = new UserInfo(1L, "2", 13);
        UserInfo userInfo2 = new UserInfo(1L, "2", 13);
        System.out.println(userInfo.equals(userInfo2));
        System.out.println(userInfo.hashCode());
        System.out.println(userInfo2.hashCode());
    }

    static String s;

    public static void main11(String[] args) {
        System.out.println(interpret("G()()()()(al)"));
    }

    /**
     * 1678. 设计 Goal 解析器
     *
     * @param command
     * @return
     */
    public static String interpret(String command) {
//        return command.replaceAll("\(\)","o").replaceAll("\(al\)","al");
        return command.replace("()", "o").replace("(al)", "al");
    }

    public static List<String> ambiguousCoordinates(String _s) {
        s = _s.substring(1, _s.length() - 1);//去除括号
        int n = s.length();
        List<String> ans = new ArrayList<>();
        for (int i = 0; i < n - 1; i++) {// 枚举逗号：在 i 的后面追加逗号
            List<String> a = search(0, i), b = search(i + 1, n - 1);
            for (String x : a) {
                for (String y : b
                ) {
                    ans.add("(" + x + "," + y + ")");
                }
            }
        }
        return ans;
    }

    private static List<String> search(int start, int end) {
        ArrayList<String> list = new ArrayList<>();
        if (start == end || s.charAt(start) != '0') {
            list.add(s.substring(start, end + 1));
        }
        for (int i = start; i < end; i++) {// 枚举小数点：在 i 后面追加小数点
            String a = s.substring(start, i + 1), b = s.substring(i + 1, end + 1);
            if (a.length() > 1 && a.charAt(0) == '0') {
                continue;
            }
            if (b.charAt(b.length() - 1) == '0') {
                continue;
            }
            list.add(a + "." + b);
        }
        return list;
    }

    public String reformatNumber(String number) {
        String s = number.replace(" ", "").replace("-", "");
        int n = s.length();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i += 3) {
            if (sb.length() != 0) {
                sb.append("-");
            }
            if (i + 5 > n) {
                if (i + 3 >= n) {
                    sb.append(s.substring(i));
                } else {
                    sb.append(s.substring(i, i + 2)).append("-").append(s.substring(i + 2));
                }
                break;
            }
            sb.append(s.substring(i, i + 3));
        }
        return sb.toString();
    }

    /**
     * 1684. 统计一致字符串的数目--hashSet
     *
     * @param allowed
     * @param words
     * @return
     */
    public int countConsistentStrings(String allowed, String[] words) {
        HashSet<Character> chars = new HashSet<>();
        for (char c : allowed.toCharArray()) {
            chars.add(c);
        }
        int ans = 0;
        int length = words.length;
        for (int i = 0; i < length; i++) {
            boolean flag = true;
            for (char c : words[i].toCharArray()) {
                if (!chars.contains(c)) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                ans++;
            }
        }
        return ans;
    }

    public int countConsistentStrings1(String allowed, String[] words) {
        int ans = 0;
        int length = words.length;
        for (int i = 0; i < length; i++) {
            boolean flag = true;
            for (int j = 0; j < words[i].length(); j++) {
                if (allowed.indexOf(words[i].charAt(j)) < 0) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                ans++;
            }
        }
        return ans;
    }

    /**
     * 764. 最大加号标志--暴力+减枝
     *
     * @param n
     * @param mines
     * @return
     */
    public static int orderOfLargestPlusSign(int n, int[][] mines) {
        int[][] map = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                map[i][j] = 1;
            }
        }
        for (int[] m : mines) {
            map[m[0]][m[1]] = 0;
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int cur = 0;
                if (map[i][j] == 0) {
                    continue;
                }
                if (i == 0 || i == n - 1 || j == 0 || j == n - 1) {
                    cur = 1;
                    ans = Math.max(cur, ans);
                    continue;
                }
                cur = findMaxSign(map, cur + 1, i, j);
                ans = Math.max(cur, ans);
            }
        }
        return ans;
    }


    private static int findMaxSign(int[][] map, int cur, int row, int col) {
        int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        while (true) {
            for (int[] d : direction) {
                int row1 = row + d[0];
                int col1 = col + d[1];
                if (row1 >= map.length || row1 < 0 || col1 >= map.length || col1 < 0) {
                    return cur;
                }
                if (map[row + d[0]][col + d[1]] != 1) {
                    return cur;
                }
                if (d[0] >= 1) {
                    d[0] += 1;
                }
                if (d[0] <= -1) {
                    d[0] -= 1;
                }
                if (d[1] >= 1) {
                    d[1] += 1;
                }
                if (d[1] <= -1) {
                    d[1] -= 1;
                }
            }
            cur++;
        }
    }

    public static void main13(String[] args) {
        int[][] mines = {{3, 0}, {3, 3}};
        System.out.println(orderOfLargestPlusSign(5, mines));
    }

    /**
     * 1704. 判断字符串的两半是否相似--双指针
     *
     * @param s
     * @return
     */
    public boolean halvesAreAlike(String s) {
        int left = 0;
        int right = s.length() - 1;
        int sumLeft = 0, sumRight = 0;
        List<Character> list = Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U');
        while (left < right) {
            if (list.contains(s.charAt(left))) {
                sumLeft++;
            }
            if (list.contains(s.charAt(right))) {
                sumRight++;
            }
            left++;
            right--;
        }
        return sumLeft == sumRight;
    }

    /**
     * 2. 两数相加
     *
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        StringBuilder builder1 = new StringBuilder();
        StringBuilder builder2 = new StringBuilder();
        while (l1 != null) {
            builder1.append(String.valueOf(l1.val));
            l1 = l1.next;
        }
        while (l2 != null) {
            builder2.append(String.valueOf(l2.val));
            l2 = l2.next;
        }
        Long numOne = Long.parseLong(builder1.reverse().toString());
        Long numTwo = Long.parseLong(builder2.reverse().toString());
        Long sum = numOne + numTwo;
        StringBuilder reverse = new StringBuilder(String.valueOf(sum)).reverse();
        ListNode head = new ListNode(-1, null);
        ListNode pre = head;
        for (int i = 0; i < reverse.length(); i++) {
            ListNode cur = new ListNode(Integer.parseInt(String.valueOf(reverse.charAt(i))), null);
            pre.next = cur;
            pre = cur;
        }
        return head.next;
    }

    public static void main15(String[] args) {
        ListNode listNode = new ListNode(2, null);
        ListNode listNode1 = new ListNode(4, null);
        ListNode listNode2 = new ListNode(3, null);
        ListNode listNode3 = new ListNode(5, null);
        ListNode listNode4 = new ListNode(6, null);
        ListNode listNode5 = new ListNode(4, null);

        listNode.next = listNode1;
        listNode1.next = listNode2;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        addTwoNumbers(listNode, listNode3);
    }

    public static void main16(String[] args) {
        String regex4 = "([01]\\d|2[0-3]):[0-5]\\d:[0-5]\\d";
        System.out.println("12:33:33".matches(regex4));
        System.out.println("12:33:33".matches(regex4));
        System.out.println("12:33:33".matches(regex4));
        System.out.println("12:33:33".matches(regex4));
        System.out.println("12:33:33".matches(regex4));
        String s = "11111324";
        String v = s.replaceAll("[1]", "v");
        System.out.println(v);
        System.out.println("123aaa321".matches("(.+).+\\1"));
        System.out.println("abc123abc".matches("(.{3}).+\\1"));
        System.out.println("aaa123aba".matches("((.)\\2*).+\\1"));
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat();
    }

    /**
     * 1.两数之差
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
            if (hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]), i};
            }
            hashtable.put(nums[i], i);
        }
        return new int[0];
    }

    /**
     * 将两个链表看成是相同长度的进行遍历，如果一个链表较短则在前面补 000，比如 987 + 23 = 987 + 023 = 1010
     * 每一位计算的同时需要考虑上一位的进位问题，而当前位计算结束后同样需要更新进位值
     * 如果两个链表全部遍历完毕后，进位值为 111，则在新链表最前方添加节点 111
     * 小技巧：对于链表问题，返回结果为头结点时，通常需要先初始化一个预先指针 pre，
     * 该指针的下一个节点指向真正的头结点head。使用预先指针的目的在于链表初始化时无可用节点值，
     * 而且链表构造过程需要指针移动，进而会导致头指针丢失，无法返回结果。
     *
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers1(ListNode l1, ListNode l2) {
        ListNode pre = new ListNode(0);
        ListNode cur = pre;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int x = l1 == null ? 0 : l1.val;
            int y = l2 == null ? 0 : l2.val;
            int sum = x + y + carry;

            carry = sum / 10;
            sum = sum % 10;
            cur.next = new ListNode(sum);

            cur = cur.next;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        if (carry == 1) {
            cur.next = new ListNode(carry);
        }
        return pre.next;
    }

    public static void main17(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        System.out.println("1111");
        Test test = new Test();
        test.test();
        Test.test2();
        Inter.test2();
    }

    /**
     * 790. 多米诺和托米诺平铺--动态规划
     *
     * @param n
     * @return
     */
    public int numTilings(int n) {
        if (n == 1) {
            return n;
        }
        long MOD = (long) 1e9 + 7;
        long[] f = new long[n + 1];
        f[0] = 1;
        f[1] = 1;
        f[2] = 2;
        for (int i = 3; i <= n; i++) {
            f[i] = (2 * f[i - 1] + f[i - 3]) % MOD;
        }
        return (int) f[n];
    }

    /**
     * 791. 自定义字符串排序
     *
     * @param order
     * @param s
     * @return
     */
    public static String customSortString(String order, String s) {
        StringBuilder builder = new StringBuilder();
        HashMap<Character, Integer> map = new HashMap<>();
        for (Character c : s.toCharArray()) {
            if (map.containsKey(c)) {
                map.put(c, map.get(c) + 1);
            } else {
                map.put(c, 1);
            }
        }
        for (int i = 0; i < order.length(); i++) {
            Character c = order.charAt(i);
            if (map.containsKey(c)) {
                int num = map.get(c);
                while (num > 0) {
                    num--;
                    builder.append(c);
                }
                map.put(c, 0);
            } else {
                break;
            }
        }
        Set<Map.Entry<Character, Integer>> entries = map.entrySet();
        for (Map.Entry<Character, Integer> set : map.entrySet()) {
            if (set.getValue() == 0) {
                continue;
            }
            Integer value = set.getValue();
            while (value > 0) {
                value--;
                builder.append(set.getKey());
            }
        }
        return builder.toString();
    }

    public static void main18(String[] args) {
        String order = "kqep";
        String s = "pekeq";
        String S = customSortString(order, s);
        System.out.println(S);
    }

    /**
     * 805. 数组的均值分割 --折半查找+二进制枚举
     *
     * @param nums
     * @return
     */
    public boolean splitArraySameAverage(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return false;
        }
        int s = Arrays.stream(nums).sum();
        for (int i = 0; i < n; i++) {
            nums[i] = nums[i] * n - s;
        }
        int m = n >> 1;
        HashSet<Integer> set = new HashSet<>();
        for (int i = 1; i < 1 << m; i++) {
            int t = 0;
            for (int j = 0; j < m; j++) {
                if (((i >> j) & 1) == 1) {
                    t += nums[j];
                }
            }
            if (t == 0) {
                return true;
            }
            set.add(t);
        }
        for (int i = 1; i < 1 << (n - m); i++) {
            int t = 0;
            for (int j = 0; j < (n - m); j++) {
                if (((i >> j) & 1) == 1) {
                    t += nums[m + j];
                }
            }
            if (t == 0 || (i != (1 << (n - m)) - 1) && set.contains(-t)) {
                return true;
            }
        }
        return false;
    }

    public static void main19(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("zhangsan,23");
        list.add("lisi,24");
        list.add("wangwu,25");
        Map<String, Integer> collect = list.stream().filter(s1 -> Integer.parseInt(s1.split(",")[1]) > 24)
                .collect(Collectors.toMap(new Function<String, String>() {
                    @Override
                    public String apply(String s) {
                        return s.split(",")[0];
                    }
                }, new Function<String, Integer>() {
                    @Override
                    public Integer apply(String s) {
                        return Integer.parseInt(s.split(",")[1]);
                    }
                }));
        Map<String, Integer> collect1 = list.stream().filter(s -> Integer.parseInt(s.split(",")[1]) > 23)
                .collect(Collectors.toMap(s -> s.split(",")[0], s -> Integer.parseInt(s.split(",")[1])));
        System.out.println(collect);
        System.out.println(collect1);
    }

    public static void main20(String[] args) {
//        ArrayList<String> list = new ArrayList<>();
//        list.add("张三1");
//        list.add("张三3");
//        list.add("张三2");
//        list.add("LISHI1");
//        list.stream()
//                .filter(s1 -> s1.length()>=3&&s1.startsWith("张")).forEach(System.out::println);
        ArrayList<String> list = new ArrayList<>();
        list.add("张三1,1");
        list.add("张三3,2");
        list.add("张三2,3");
        list.add("LISHI1,5");
        List<Student> collect = list.stream().map(s -> new Student(s.split(",")[0], Integer.parseInt(s.split(",")[1])))
                .collect(Collectors.toList());
        System.out.println(collect);
        list.stream().map(Student::new).collect(Collectors.toList()).forEach(System.out::println);
        Student[] strings = list.stream().map(Student::new).toArray(Student[]::new);
        System.out.println(Arrays.toString(strings));
        String[] strings1 = list.stream().map(s1 -> s1.split(",")[0]).toArray(String[]::new);
        System.out.println(Arrays.toString(strings1));
        String[] strings2 = list.stream().map(s1 -> new Student(s1.split(",")[0], Integer.parseInt(s1.split(",")[1])))
                .map(Student::getName).toArray(String[]::new);
        System.out.println(Arrays.toString(strings2));
        String[] strings3 = list.stream().map(Student::new).map(student -> student.getName() + "-" + student.getAge())
                .toArray(String[]::new);
        System.out.println(Arrays.toString(strings3));
    }

    public static void main21(String[] args) {
        int[][] t = {{5, 10}, {2, 5}, {4, 7}, {3, 9}};
        System.out.println(maximumUnits(t, 10));
    }

    /**
     * 1710. 卡车上的最大单元数--贪心算法+排序
     *
     * @param boxTypes
     * @param truckSize
     * @return
     */
    public static int maximumUnits(int[][] boxTypes, int truckSize) {
        Arrays.sort(boxTypes, (o1, o2) -> o2[1] - o1[1]);
        int ans = 0;
        for (int[] t : boxTypes) {
            if ((truckSize -= t[0]) > 0) {
                ans += (t[0] * t[1]);
            } else {
                ans += (truckSize += t[0]) * t[1];
                break;
            }
        }
        return ans;
    }

    public static void main22(String[] args) {
        int[] nums = {2, 0, 1};
        System.out.println(isIdealPermutation(nums));
    }

    /**
     * 775. 全局倒置与局部倒置--根据前缀的最大值来判断
     *
     * @param nums
     * @return
     */
    public static boolean isIdealPermutation(int[] nums) {
        int max = nums[0];
        for (int i = 2; i < nums.length; i++) {
            if (nums[i] < max) {
                return false;
            }
            max = Math.max(max, nums[i - 1]);
        }
        return true;
    }

    /**
     * 775. 全局倒置与局部倒置--根据偏移的差值来判断
     *
     * @param nums
     * @return
     */
    public static boolean isIdealPermutation1(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (Math.abs(nums[i] - i) > 1) {
                return false;
            }
        }
        return true;
    }

    /**
     * 792. 匹配子序列的单词数--分桶
     * 方法一：分桶
     * 题目中字符串 sss 的数据规模最高达到 5×1045 \times 10^45×104，
     * 如果暴力枚举 wordswordswords 中的每个字符串 www，判断其是否为 sss 的子序列，很有可能会超时。
     * 我们不妨将 wordswordswords 中的所有单词根据首字母来分桶，
     * 即：把所有单词按照首字母分到 26 个桶中，每个桶中存储的是所有以该字母开头的所有单词。
     *
     * @param s
     * @param words
     * @return
     */
    public static int numMatchingSubseq(String s, String[] words) {
        Deque<String>[] deques = new Deque[26];
        for (int i = 0; i < 26; i++) {
            deques[i] = new ArrayDeque<>();
        }
        for (String w : words) {
            deques[w.charAt(0) - 'a'].add(w);
        }
        int ans = 0;
        for (char c : s.toCharArray()) {
            Deque<String> deque = deques[c - 'a'];
            for (int i = deque.size(); i > 0; i--) {
                String tmp = deque.poll();
                if (tmp.length() == 1) {
                    ans++;
                } else {
                    deques[tmp.charAt(1) - 'a'].offer(tmp.substring(1));
                }
            }
        }
        return ans;
    }

    /**
     * 超时
     *
     * @param s
     * @param words
     * @return
     */
    public static int numMatchingSubseq1(String s, String[] words) {
        int ans = 0;
        for (String s1 : words) {
            String tmp = s;
            boolean flag = true;
            for (int i = 0; i < s1.length(); i++) {
                char c = s1.charAt(i);
                if (!tmp.contains(String.valueOf(c))) {
                    flag = false;
                    break;
                }
                tmp = tmp.substring(tmp.indexOf(c) + 1);
            }
            if (flag) {
                ans++;
            }
        }
        return ans;
    }

    public static void main23(String[] args) {
        String s = "dsahjpjauf";
        String[] words = {"ahjpjau", "ja", "ahbwzgqnuk", "tnmlanowax"};
        System.out.println(numMatchingSubseq(s, words));
    }

    public static void main24(String[] args) {
        int[] nums = {2, 1, 3};
        System.out.println(sumSubseqWidths(nums));
    }

    /**
     * 891. 子序列宽度之和
     * 根据题目描述我们可以知道，计算宽度的时候，只是需要计算序列中【最大元素】与【最小元素】的差值。
     * 那么我们只需要关心数组nums中数字的大小而不需要关心它所在的位置了，即：子序列[2,4]与子序列[4,2]差值都是2。
     *
     * @param nums
     * @return
     */
    public static int sumSubseqWidths(int[] nums) {
        Arrays.sort(nums);
        int mod = (int) 1e9 + 7;
        int length = nums.length;
        long ans = 0;
        long[] pow = new long[length];
        pow[0] = 1;
        for (int i = 1; i < length; i++) {
            pow[i] = (pow[i - 1] << 1) % mod;
        }
        for (int i = 0; i < length; i++) {
            ans = (ans + (pow[i] - pow[length - i - 1]) * nums[i] % mod) % mod;
        }
        return (int) ans;
    }

    /**
     * 1732. 找到最高海拔--简单模拟
     *
     * @param gain
     * @return
     */
    public int largestAltitude(int[] gain) {
        int length = gain.length;
        int[] tmp = new int[length + 1];
        tmp[0] = 0;
        int ans = 0;
        for (int i = 1; i < tmp.length; i++) {
            tmp[i] = tmp[i - 1] + gain[i - 1];
            if (tmp[i] > ans) {
                ans = tmp[i];
            }
        }
        return ans;
    }

    /**
     * 括号字符串的最长有效长度
     *
     * @param args
     */
    public static void main25(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.next();
        int length = longestValidParentheses(str);
        System.out.println(length);
    }

    public static int longestValidParentheses(String s) {
        int max = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    max = Math.max(max, i - stack.peek());
                }
            }
        }
        return max;
    }

    /**
     * 在其它数出现次数都为偶数的数组中找到出现次数为奇数次的数
     *
     * @param args
     */
    public static void main26(String[] args) {
        Scanner scanner = new Scanner(System.in);
        HashSet<Integer> set = new HashSet<>();
        int n = scanner.nextInt();
        while (n > 0) {
            n--;
            int cur = scanner.nextInt();
            if (set.contains(cur)) {
                set.remove(cur);
            } else {
                set.add(cur);
            }
        }
        Object[] s = set.toArray();
        System.out.println(s[0]);
    }

    public static void main27(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int length = scanner.nextInt();
        int[] nums = new int[length];
        for (int i = 0; i < length; i++) {
            nums[i] = scanner.nextInt();
        }
        Arrays.sort(nums);
        for (int i = 0; i < length; i++) {
            System.out.print(nums[i] + " ");
        }
    }

    //使用long，int相加会越界
    public static void main28(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = Integer.parseInt(in.nextLine());
        long[] nums = new long[n];
        String[] temp = in.nextLine().split(" ");
        for (int i = 0; i < n; i++) {
            nums[i] = Long.parseLong(temp[i]);
        }

        //最小堆
        PriorityQueue<Long> pq = new PriorityQueue<>();
        for (long num : nums) {
            pq.offer(num);
        }


        long res = 0;
        while (pq.size() > 1) {
            //取出两个最小的
            long cost = pq.poll() + pq.poll();
            res += cost;
            pq.offer(cost);
        }

        System.out.println(res);
    }

/**
 七刷
 解题思路：
 1. 先用中序遍历遍历树，得到一个部分排序数组，该数组中有两个数交换了位置，
 现在的问题变成了从一个部分有序的数组中找出交换了位置的那两个数

 2. 因为此时的情况必定是一个小的数放到了后面，一个大的数放到了前面
 所以从左往右找那个大的数，并记录下索引，从右往左找小的那个数，并且索引值必大于前面记录下的索引
 */

//
//    List<Integer> list = new ArrayList();
//    public int[] findError (TreeNode root) {
//        int[] result = new int[2];
//        if(root == null) {
//            return result;
//        }
//        findErrorHelper(root);
//        int i, j;
//        for(i = 0; i < list.size() - 1; i++) {
//            if(list.get(i) > list.get(i + 1)) {
//                result[1] = list.get(i);
//                break;
//            }
//        }
//        for(j = list.size() - 1; j > i; j--) {
//            if(list.get(j) < list.get(j - 1)) {
//                result[0] = list.get(j);
//                break;
//            }
//        }
//        return result;
//    }
//
//    private void findErrorHelper(TreeNode root) {
//        if(root != null) {
//            findErrorHelper(root.left);
//            list.add(root.val);
//            findErrorHelper(root.right);
//        }
//    }
public static void main29(String[]args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int k = scanner.nextInt();

    int arr[] = new int[n];
    for (int i = 0; i < n; i++)
        arr[i] = scanner.nextInt();
    int l = 0;
    int r = n - 1;
    int m = l + 1;
    while (l < r - 1) {
        //l++;
        if (l == 0 || arr[l] != arr[l - 1]) {
            //l不重复在比较m,r
            m = l + 1;
            r = n - 1;
            while (m < r) {
                if (arr[l] + arr[m] + arr[r] == k) {
                    if ((m == 0 || arr[m] != arr[m - 1]) && arr[m] != arr[r])
                        System.out.println(arr[l] + " " + arr[m] + " " + arr[r]);
                    m++;
                    r--;
                } else if (arr[l] + arr[m] + arr[r] < k)
                    m++;
                else r--;
            }
        }
        l++;
    }
}

    /**
     *  score 分数
     *  upCount 大写字母数目
     *  lowCount 小写字母数目
     *  numCount 数字数目
     *  sigCount 符号数目
     */
    public static void main30(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNextLine()){
            String passwd = in.nextLine();
            char[] ch = passwd.toCharArray();
            //1.长度超过8位
            int len = ch.length;
            if(len <= 8) {
                System.out.println("NG");
                continue;
            }
            //遍历获取大小写字母、数字、符号数目
            int upCount = 0,lowCount = 0, numCount = 0,sigCount = 0;

            for (int i = 0; i < len; i++) {
                if (Character.isUpperCase (ch[i])) {
                    upCount = 1;
                } else if (Character.isLowerCase (ch[i])) {
                    lowCount = 1;
                } else if (Character.isDigit (ch[i])) {
                    numCount = 1;
                } else {
                    sigCount = 1;
                }
            }

            //2.包括大小写字母.数字.其它符号,以上四种至少三种
            if(upCount + lowCount + numCount + sigCount < 3) {
                System.out.println("NG");
                continue;
            }

            //3.不能有长度大于2的包含公共元素的子串重复 （注：其他符号不含空格或换行)
            //判断3个重复即可，超过3个重复的，肯定都满足3个重复的。
            if (getString(passwd)) {
                System.out.println("NG");
                continue;
            }
            System.out.println("OK");
        }
    }

    private static boolean getString(String passwd) {
        for (int i = 0; i+3 < passwd.length(); i++) {
            if (passwd.substring (i+1).contains (passwd.substring (i,i+3))){
                return true;
            }
        }
        return false;
    }

    public int search(int[] nums, int target) {
        // write code here
        int index = -1;
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) {
                // 在low 到 mid之间找第一个下标
                index = mid;
                high = mid - 1;
            } else if (target > nums[mid]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return index;
    }
    /**
     * 1732. 找到最高海拔--前缀和
     *
     * @param gain
     * @return
     */
    public int largestAltitude1(int[] gain) {
        int ans = 0, h = 0;
        for (int tmp : gain) {
            h += tmp;
            ans = Math.max(ans, h);
        }
        return ans;
    }
}

